package com.cat.chapter035;

import java.util.HashMap;

/**
 * @author cat
 * @description https://leetcode.cn/problems/lru-cache/description/
 * @create 2025/5/29 21:48
 * @since JDK17
 */
public class Code02LRU {
    private final int capacity;
    private HashMap<Integer, DoubleNode> map = new HashMap<>();
    private NodeList list = new NodeList();

    // 双向节点
    class DoubleNode {
        DoubleNode last;
        DoubleNode next;
        int val;
        int key;
        public DoubleNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // 实现双向链表
    class NodeList {
        DoubleNode head;
        DoubleNode tail;

        // 最普通的情况
        void addNode(DoubleNode node) {
            if (head == null) { // 第一个
                head = tail = node;
                return;
            }
            tail.next = node;
            node.last = tail;
            tail = node;
        }

        // 删除头节点
        void removeNode() {
            if (head == tail) {
                head = tail = null;
                return;
            }
            DoubleNode ans = head;
            head = head.next;
            ans.next = null;
            head.last = null;
        }

        // 移动节点到最后一个
        void moveNodeToLast(DoubleNode node) {
            if (node == tail) { // 本来就在尾部，不用管
                return;
            }
            if (head == node) { // 头部
                DoubleNode next = head.next;
                next.last = null;
                head.next = null;
                tail.next = head;
                head.last = tail;
                tail = head;
                head = next;
            } else {
                DoubleNode last = node.last;
                DoubleNode next = node.next;
                last.next = next;
                next.last = last;
                tail.next = node;
                node.last = tail;
                node.next = null;
                tail = node;
            }
        }
    }

    public Code02LRU(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        DoubleNode node = map.get(key);
        if (node == null) { // 没有该值
            return -1;
        }
        list.moveNodeToLast(node); // 先把该值移动到最后
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) { // 存在
            DoubleNode node = map.get(key);
            node.val = value;   // 改val的值
            list.moveNodeToLast(node); // 直接移动到最后
        } else { // 不存在
            DoubleNode node = new DoubleNode(key, value);
            if (map.size() == capacity) { // 满了
                map.remove(list.head.key); // 将值从map中删除
                list.removeNode(); // 把第一个删除
            }
            map.put(key, node);
            list.addNode(node);
        }
    }
}
